package tul.cot.util;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import tul.cot.MigrationTree;



public class TreeUtils {

	public static class TimeCmp implements Comparator<MigrationTree> {
		
		public static final Comparator<MigrationTree> instance = new TimeCmp(); 

		private TimeCmp() {}
			
		@Override
		public int compare(MigrationTree t1, MigrationTree t2) {
			if (t1.getTime() > t2.getTime())
				return -1;
			if (t1.getTime() < t2.getTime())
				return 1;
			return 0;
		}
		
	}
	
	public static List<MigrationTree> sortNodes(MigrationTree root) {
		List<MigrationTree> ret = new ArrayList<MigrationTree>(1000);
		PriorityQueue<MigrationTree> queue = new PriorityQueue<MigrationTree>(1000, TimeCmp.instance);
		
		queue.add(root);
		while (!queue.isEmpty()) {
			MigrationTree tree = queue.poll();
			ret.add(tree);
			for (MigrationTree son: tree.getSons()) {
				queue.add(son);
			}
		}
		
		return ret;
		
	}
}